package com.wbt.huawei.c20220717;

import java.util.*;

public class HJ44 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int[][] nums = new int[9][9];

            for (int i =0 ;i<9;i++){
                for (int j=0 ;j<9;j++){
                   nums[i][j] = sc.nextInt();
                }
            }
            solveSudoku(nums);
            print(nums);
        }
    }


    //
    public static boolean solveSudoku(int[][] board){
        for (int i =0 ;i<9;i++){
            for (int j=0 ;j<9;j++){
                if(board[i][j] != 0){ // 跳过原始数字
                    continue;
                }
                List<Integer> integers = perSolve(i, j, board);
                if(integers.size() == 0){
                    return false;
                }else {
                    for (int k:integers){
                        board[i][j] = k;//将k放在（i，j）
                        if (solveSudoku(board)){ // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = 0;//回溯
                    }
                    return false;
                }
            }
        }

        return true;
    }

    public static List<Integer> perSolve(int row, int col, int[][] board){
        Set<Integer> hasNums = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            list.add(i + 1);
            if (board[row][i] != 0){
                hasNums.add(board[row][i]);
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] != 0){
                hasNums.add(board[j][col]);
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] != 0){
                    hasNums.add(board[i][j]);
                }
            }
        }

        list.removeAll(hasNums);
        return new ArrayList<>(list);
    }

    // 输出二维矩阵
    public static void print(int[][] nums){
        for (int i =0 ;i<9;i++){
            for (int j=0 ;j<8;j++){
                System.out.print(nums[i][j] + " ");
            }
            System.out.println(nums[i][8]);
        }
    }
}
